CD-ROMs are a form of high capacity storage. Data is stored in a single track on a CD-ROM. The track is divided into sectors. Reading data from a CD-ROM requires knowledge of the volume number of the CD-ROM (if there is more than one CD-ROM) and the sector number in which the data is stored on the CD-ROM. For example, a CD-ROM file system typically requests a read by providing a volume number and a sector number to a CD-ROM driver that controls reading the data from the CD-ROM. As with any form of storage medium, reading data from a CD-ROM is time consuming. Thus, it is advantageous to reduce the amount of time spent reading data from a CD-ROM.
One technique for reducing the amount of time spent reading data from a CD-ROM is caching. Through the use of caching, a CD-ROM driver stores in a CD-ROM cache data that has recently been requested from a CD-ROM and data that is expected to be requested next. The CD-ROM cache is typically located in RAM. Then, when a request is received to read data, the CD-ROM driver first determines whether the data is stored in the CD-ROM cache. If the data is stored in the cache (known as a cache hit), the data can be read from the cache in RAM, instead of from the CD-ROM. If the data is not stored in the cache (known as a cache miss), the data must be read from the CD-ROM. Because a read from the cache in RAM is quicker than a read from the CD-ROM, the amount of time spent completing the read is reduced if there is a cache hit. The more often the cache has a hit (as opposed to a miss), the more efficient the cache is. The frequency with which the cache has hits is determined by how good the CD-ROM driver is at predicting which data (i.e., volume number and sector number) will be requested next and, thus, which data to store in the cache.
CD-ROM drivers and other device drivers use various techniques to predict which data will be requested next. For example, one common type of caching technique stores data that has recently been requested. This type of caching technique also stores data that is adjacent to the requested data on the CD-ROM. The adjacent data is stored based on the assumption that once data at a particular location on the CD-ROM has been requested, it is likely that the data adjacent to the requested data will be requested next. This assumption is valid with CD-ROMs because data is typically accessed sequentially or serially (as opposed to randomly) from CD-ROMs. The process of reading the additional adjacent data and storing it in the cache is known as prefetching. The CD-ROM driver reads the data before it has been requested in anticipation that the data will be requested next. As new data is requested and prefetched, the CD-ROM driver replaces the least recently used ("LRU") data in the cache with the new data. This type of caching technique is known as LRU caching. Another common type of caching technique assigns priorities to the various types of data that are stored on the CD-ROM and replaces the various types of data in the cache based on the assigned priorities. This type of caching technique is known as prioritized caching.
While the use of any cache is more efficient than the use of no cache, it is always desirable to increase the number of cache hits and, thus, the efficiency of the cache. As discussed above, the determination of which data to store in the cache controls how efficient the cache is. Thus, a method and system for caching data that improve the efficiency of the cache are desired.